package william.dp;


/**
 * @author ZhangShenao
 * @date 2024/3/30
 * @description <a href="https://leetcode.cn/problems/house-robber/">...</a>
 */
public class Leetcode198_打家劫舍 {
    /**
     * 采用动态规划算法
     * 定义状态:状态state[i]表示以i为起点的房屋nums[i,N-1]范围内可偷取的最大值
     * 状态转移公式:state[i]=Max{nums[i]+state[i+2],nums[i+1]+state[i+3],...,nums[N-2],nums[N-1]}
     * 从后往前生成状态数组
     * <p>
     * 时间复杂度O(N^N) 双重遍历数组
     * 空间复杂度O(N) 额外申请了一个状态数组,长度为N
     */
    public int rob(int[] nums) {
        //边界条件校验
        if (nums == null || nums.length < 1) {
            return 0;
        }

        //构造状态数组
        //state[i]表示以i为起点的房屋nums[i,N-1]范围内可偷取的最大值
        int N = nums.length;
        int[] state = new int[N];

        //定义初始状态
        state[N - 1] = nums[N - 1];

        //状态转移
        //state[i]=Max{nums[i]+state[i+2],nums[i+1]+state[i+3],...,nums[N-2],nums[N-1]}
        for (int i = N - 2; i >= 0; i--) {
            for (int j = i; j < N; j++) {
                int nextState = (j < N - 2 ? state[j + 2] : 0);
                state[i] = Math.max(state[i], (nums[j] + nextState));
            }
        }

        //返回state[0]
        return state[0];

    }
}
